//给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为
//每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。 
//
// 
//
// 示例 1: 
//
// 
//输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
//输出: 16 
//解释: 这两个单词为 "abcw", "xtfn"。 
//
// 示例 2: 
//
// 
//输入: ["a","ab","abc","d","cd","bcd","abcd"]
//输出: 4 
//解释: 这两个单词为 "ab", "cd"。 
//
// 示例 3: 
//
// 
//输入: ["a","aa","aaa","aaaa"]
//输出: 0 
//解释: 不存在这样的两个单词。
// 
//
// 
//
// 提示： 
//
// 
// 2 <= words.length <= 1000 
// 1 <= words[i].length <= 1000 
// words[i] 仅包含小写字母 
// 
// Related Topics 位运算 数组 字符串 
// 👍 198 👎 0

package com.cute.leetcode.editor.cn;
public class MaximumProductOfWordLengths {
    public static void main(String[] args) {
        String[] words = {"abcw","baz","foo","bar","xtfn","abcdef"};
        new MaximumProductOfWordLengths().new Solution().maxProduct(words);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 咋说呢，我就不觉得这道题和位运算有什么关系，我只会遍历，时间复杂度高的一匹，我都懒得提交了（时间空间均7%）
         *
         * 题解，使用int的前26位储存每个单词中字母的出现情况，遍历还是需要遍历，只是判断是否重复的时候快了非常多
         * 如果两个word出现了相同的字母，&之后绝对不为0
         */
        public int maxProduct(String[] words) {
            /*int res = 0;
            boolean flag = false;
            for (int i = 0; i < words.length-1; i++) {
                for (int j = i+1; j < words.length ; j++) {
                    for (int k = 0; k <words[i] .length() ; k++) {
                        if (words[j].contains((words[i].substring(k, k+1)))){
                            flag = true;
                            break;
                        }
                    }
                    if (!flag) res = Math.max(res,words[i].length()*words[j].length());
                    flag = false;
                }
            }
            return res;*/
            int[] ans = new int[words.length];
            for (int i = 0; i < words.length; i++) {
                for (char c : words[i].toCharArray())
                    // 这个是用int的32位存储的字母出现情况
                    ans[i] |= 1 << ( c - 'a');//统计当前单词字母出现情况，在相应位赋1
            }
            int res = 0;
            for (int i = 0; i < words.length-1; i++) {
                for (int j = i+1; j < words.length ; j++) {
                    if ((ans[i]&ans[j]) == 0){
                        res = Math.max(res, words[i].length() * words[j].length());
                    }
                }
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}